๐งท Deadlock
๋ฐ๋๋ฝ์ด๋, ํ๋ก์ธ์ค๊ฐ ์์์ ์ป์ง ๋ชปํด ๋ค์ ์ฒ๋ฆฌ๋ฅผ ํ์ง ๋ชปํ๋ ์ํ๋ก, "๊ต์ฐฉ ์ํ" ๋ผ๊ณ ๋ ํ๋ฉฐ ์์คํ ์ ์ผ๋ก ํ์ ๋ ์์์ ์ฌ๋ฌ ๊ณณ์์ ์ฌ์ฉํ๋ ค ํ ๋ ๋ฐ์ํ๋ค.
- ์์คํ ์ ์ ํํ ์์์ ๊ฐ์ง๋ค. (CPU cycles, Files, I/O devices, locks) ๊ทธ๋ฆฌ๊ณ ๊ทธ๋ ๊ธฐ ๋๋ฌธ์ ๋ฐ๋๋ฝ์ด ๋ฐ์ํ ์ ์๋ ๊ฒ์ด๋ค.
- Deadlocked๋ ๋ชจ๋ ํ๋ก์ธ์ค๊ฐ ๋ค๋ฅธ ํ๋ก์ธ์ค์ ์ํด ๋ฐ์๋ ์ ์๋ ์ด๋ฒคํธ๋ฅผ ๊ธฐ๋ค๋ฆฌ๊ณ ์๋ ์ํ๋ผ๊ณ ๋ ํ ์ ์๋ค.
๐ช ๋ฐ์ ์กฐ๊ฑด
๋ฐ๋๋ฝ์ ์ธ์ ๋ฐ์ํ ์ ์์๊น? ์๋์ ๋ค ๊ฐ์ง ์กฐ๊ฑด์ด ๋์์ ์ฑ๋ฆฝํ ๋ ๋ฐ์ํ๋ค. ํ๋๋ผ๋ ์ฑ๋ฆฝํ์ง ์๋๋ก ํ๋ฉด, ๊ต์ฐฉ ์ํ๋ฅผ ํผํ ์ ์๋ ๊ฒ์ด๋ค.
์ํธ ๋ฐฐ์ (Mutual Exclusion)
- ์์์ ํ ๋ฒ์ ํ ํ๋ก์ธ์ค๋ง์ด ์ฌ์ฉํ ์ ์์ด์ผ ํ๋ค. ์ ์ด๋ ํ๋์ ์์์ ๊ณต์ ๋์ง ์์์ผ ํ๋ค.
์ ์ ๋๊ธฐ(Hold and Wait)
- ์ ์ด๋ ํ๋์ ์์์ ํ ๋นํ๊ณ ์์ด์ผ ํ๊ณ , ๋ค๋ฅธ ํ๋ก์ธ์ค๋ค์ ์กํ์๋ ์์์ ์ ์ ํ๊ธฐ ์ํด ๋๊ธฐํ๋ ํ๋ก์ธ์ค๊ฐ ์์ด์ผ ํ๋ค.
๋น์ ์ (No Preemption)
- ๋ค๋ฅธ ํ๋ก์ธ์ค์ ํ ๋น๋ ์์์ ์ฌ์ฉ์ด ๋๋ ๋๊น์ง ๊ฐ์ ๋ก ์ ์ ํ ์ ์์ด์ผ ํ๋ค.
์ํ ๋๊ธฐ(Circular Wait)
- ํ๋ก์ธ์ค ์งํฉ์์ P0์ P1์ด ์ ์ ํ ์์์ ๋๊ธฐํ๊ณ , P1์ P2๊ฐ ์ ์ ํ ์์์ ๋๊ธฐ, ์ด๊ฐ ๋ฐ๋ณต๋์ด Circle์ ์์ฑํ๋ค.
- ์ด๋ ์ ์ ๋๊ธฐ๋ก ์ธํด ๋ฐ์ํ ์ ์๋ค.
์์ ํ ๋น ๊ทธ๋ํ๋ฅผ ๊ทธ๋ ค๋ณด์์ ๋, ์ฌ์ดํด์ด ์์ฑ๋๋ค๋ฉด ๋ฐ๋๋ฝ์ด ์กด์ฌํ ์๋ ์๋ค. ์ด๋ ๊ทธ์ ๊ฐ๋ฅ์ฑ์ด ์์์ ์๋ฏธํ๊ธฐ์ ๋ฐ๋๋ฝ์ด ์กด์ฌํ์ง ์์ ์๋ ์๋ค.
- ํ์ง๋ง ์ฌ์ดํด์ด ์๋ค๋ฉด, ๋ฐ๋๋ฝ์ด ๋ฐ์ํ์ง ์๋๋ค๋ ๊ฒ์ ๋ณด์ฅํ๋ค.
๐งท Deadlock ์ฒ๋ฆฌ
๋ค์๊ณผ ๊ฐ์ ์ ๋ต์ด ์๋ค.
๋ฐ๋๋ฝ์ ๋ฐฉ์งํ๊ฑฐ๋ ํผํ๊ธฐ ์ํ ํ๋กํ ์ฝ์ ์ฌ์ฉ
- ์์คํ ์ด ์ ๋๋ก ๋ฐ๋๋ฝ์ ๋ค์ด๊ฐ์ง ์๋๋ก ๋ณด์ฅํ๋ค.
-
Deadlock prevention๊ณผ Deadlock avoidance๊ฐ ์๋ค.
- avoidance๋ฅผ ์ํด์๋ ์ถ๊ฐ์ ์ธ ์ ๋ณด๊ฐ ํ์ํ๋ค.
์์คํ ์ด ๋ฐ๋๋ฝ์ ๋ค์ด๊ฐ๋ ๊ฒ์ ํ์ฉํ๋, ์ด๋ฅผ ๊ฐ์งํ๊ณ ๋ณต๊ตฌ
๋ฐ๋๋ฝ์ ๋ฐ์์ ์ ์ฒ๋ฆฌํ์ง ์๋๊ฐ? ๋๋ถ๋ถ์ ์์คํ ์ ๋ฐ๋๋ฝ์ด ์ ๋ฐ์ํ์ง ์์ผ๋ฉฐ, ๋ฐ๋๋ฝ ์๋ฐฉ, ํํผ, ํ์ง ๋ฐ ๋ณต๊ตฌํ๋ ๊ฒ์ ๋น์ฉ์ด ๋ง์ด ๋ ๋ค.
๋ฐ๋๋ฝ ๋ฌด์
- ๊ฐ์ฅ ๋ง์ด ์ฌ์ฉํ๋ ๋ฐฉ๋ฒ
๐ช Deadlock Prevention
๋ฐ๋๋ฝ์ ๋ฐ์ ์กฐ๊ฑด 4๊ฐ์ง๊ฐ ๋ชจ๋ ์ฑ๋ฆฝ๋์ด์ผ ๋ฐ์ํ๋ค. ๋ฐ๋ผ์ ํ ๊ฐ์ง ์กฐ๊ฑด๋ง ์ฑ๋ฆฝ๋์ง ์๋๋ผ๋ ๋ฐ์ํ์ง ์๋๋ค. ๋ฐ๋๋ฝ ์๋ฐฉ์ ์ ์ด๋ ํ ๊ฐ์ง ์กฐ๊ฑด์ด ์ฑ๋ฆฝํ์ง ์๋๋ค๊ณ ๋ณด์ฅํ๋ค.
- ๊ฐ 4๊ฐ์ง ์กฐ๊ฑด์ ๋ํ ๋ถ์ ์ ํตํด ๋ฐ๋๋ฝ์ ์๋ฐฉํ๋๋ก ํ๋ ๋ฐฉ๋ฒ์ด๋ค.
Mutual Exclusion - ์ํธ ๋ฐฐ์
- ๋ฉํฐ ํ๋ก์ธ์ค๊ฐ ์์์ ๊ณต์ ํ๋๋ก ํ์ฌ ์ํธ ๋ฐฐ์ ๋ฅผ ๋ถ์ ํ ์ ์๋ค.
- ์์์ ๊ณต์ ๊ฐ ๊ฐ๋ฅํ๋๋ก ๋ง๋ ๋ค. (ex. read-only file : ์ฌ๋ฌ ํ๋ก์ธ์ค๊ฐ ์ฝ๊ธฐ ๊ฐ๋ฅํ๋ค.)
- ํ์ง๋ง, ์์์ ๊ณต์ ๊ฐ ๊ฐ๋ฅํ๋๋ก ๋ง๋๋ ๊ฒ์ด ์ด๋ ต๋ค.
Hold and Wait - ์ ์ ๋๊ธฐ
-
์ํธ ๋ฐฐ์ ๋ฅผ ๋ถ์ ํ๋ ๊ฒ๋ณด๋ค๋ ์ฌ์ด ๋ฐฉ๋ฒ์ผ๋ก, ๋ ๊ฐ์ง ๋ฐฉ๋ฒ์ด ์๋ค.
- ๋ชจ๋ ํ๋ก์ธ์ค๊ฐ ์คํ ์ ์ ํ์ํ ์์์ ๋ชจ๋ ์์ฒญํ์ฌ ํ ๋น๋ฐ๋๋ก ํ๋ ๊ฒ์ด๋ค. ํ์ง๋ง ์ด๋ ๋ฎ์ ์์ ํ์ฉ๋๊ฐ ๋ฌธ์ ๊ฐ ๋๋ค.
- ๋ชจ๋ ํ๋ก์ธ์ค๊ฐ ์์์ ํ๋๋ ๊ฐ์ง๊ณ ์์ง ์์ ๊ฒฝ์ฐ์๋ง ์์์ ์์ฒญํ๋๋ก ํ๋ค. (์์์ ์ป๊ณ , ์ฌ์ฉํ๊ณ ํด์ , ๋ ์ป๊ณ ์ฌ์ฉํ๊ณ ํด์ , ์ด๋ฅผ ๋ฐ๋ณต) ํ์ง๋ง ์ด๋ Starvation์ด ๋ฌธ์ ๊ฐ ๋๋ค.
No Preemption - ๋น์ ์
- ์์์ ์ ์ ํ๊ณ ์๋ ํ๋ก์ธ์ค๊ฐ ๋ค๋ฅธ ์์์ ์๊ตฌํ ๋, ์ ์ ํ๊ณ ์๋ ๋ชจ๋ ์์์ ๋ฐ๋ฉํ๊ณ , ์๊ตฌํ ์์์ ์ฌ์ฉํ๊ธฐ ์ํด ๊ธฐ๋ค๋ฆฌ๊ฒ ํ๋ค.
- ์์์ด ์ ์ ๊ฐ๋ฅํ ๊ฒฝ์ฐ์๋ง ๊ฐ๋ฅํ๋ค.
Circular Wait - ์ํ ๋๊ธฐ
- ๋ชจ๋ ์์์ ์์๋ฅผ ์ ํ๊ณ , ํ๋ก์ธ์ค๊ฐ ์ด ์์์ ๋ง๊ฒ ์์์ ์์ฒญํ๋๋ก ํ๋ค.
๋ฐ๋๋ฝ ์๋ฐฉ์ ์์์ ๋ญ๋น๊ฐ ์ฌํ๋ค๋ ๋จ์ ์ด ์๋ค.
๐ช Deadlock Avoidance
๋ฐ๋๋ฝ์ด ๋ฐ์ํ๋ฉด ์ด๋ฅผ ํผํ๋ ๋ฐฉ๋ฒ์ด๋ค.
- ์์์ด ์ด๋ป๊ฒ ์์ฒญ๋๋์ง์ ๋ํ ์ถ๊ฐ ์ ๋ณด๊ฐ ํ์ํ๋ค.
- ๊ฐ ์์ฒญ๋ง๋ค, ์์ฒญ์ด ๋ฐ์๋ค์ฌ์ง์ง, ๋๊ธฐํ ์ง๋ฅผ ๊ฒฐ์ ํ๋ค.
- ์ ๋ณด์ ์๊ณผ ์ ํ์ ๋ฐ๋ผ ๋ค์ํ ์๊ณ ๋ฆฌ์ฆ์ด ์ ์ฉ๋ ์ ์๋ค.
Safe state
-
์ด ์ํ์์๋, ์์คํ ์ ๊ฐ ํ๋ก์ธ์ค์ ์์์ ํ ๋นํ ์ ์๊ณ , ๋ฐ๋๋ฝ์ ํผํ ์ ์๋ค.
- ๋ชจ๋ ์์ฒญ์ ๋ง์กฑํ ์ ์๋ Safe sequence(ํ๋ก์ธ์ค์ ์์)๊ฐ ์๋ ๊ฒฝ์ฐ์๋ง ๊ฐ๋ฅํ๋ค.
Unsafe state
- safeํ์ง ์์ ์ํ๋ก, ๋ฌด์กฐ๊ฑด ๋ฐ๋๋ฝ์ ์๋ฏธํ๋ ๊ฒ์ ์๋๋ค.
- ํ์ง๋ง ๋ฐ๋๋ฝ์ด ๋ฐ์ํ ์ ์๋ ์ํ์ด๋ค.
Resource-Allocation-Graph ์๊ณ ๋ฆฌ์ฆ
- ์์ ํ ๋น ๊ทธ๋ํ๊ฐ ์ฌ์ดํด์ ์์ฑํ๋ ์ฌ๋ถ๋ฅผ ํ์ ํด์ผ ํ๋ค.
-
ํด๋น ์๊ณ ๋ฆฌ์ฆ์ ์ํด์๋ Claim edge์ Request edge๋ฅผ ์ฌ์ฉํ๋ค.
- Claim edge๋ ํน์ ํ๋ก์ธ์ค๊ฐ ํน์ ์์์ ๋ฏธ๋์ ์์ฒญํ ๊ฒ์์ ๋ํ๋ธ๋ค.
- Request edge๋ ํน์ ํ๋ก์ธ์ค๊ฐ ํน์ ์์์ ์์ฒญํจ์ ๋ํ๋ธ๋ค.
- Claim edge๋ ์ค์ ๋ก ํด๋น ์์ฒญ์ด ๋ฐ์ํ์ ๋ Request edge๋ก ๋ณ๊ฒฝ๋๋ค. ๊ทธ๋ฆฌ๊ณ ํด๋น ์์์ ํด์ ํ๋ฉด ๋ค์ Claim edge๋ก ๋ณ๊ฒฝ๋๋ค.
- ํด๋น edge๋ค์ด ์ฌ์ดํด์ ํ์ฑํ๋ค๋ฉด ์์์ ํ ๋น์ด ๋ถ๊ฐ๋ฅํ๋๋ก ํ๋ค.
Banker's ์๊ณ ๋ฆฌ์ฆ
-
Resource-Allocation-Graph ์๊ณ ๋ฆฌ์ฆ์ multi-resource ๋ฌธ์ ์์ ์ ์ฉ ๋ถ๊ฐ๋ฅํ๋ค.
- ์ฌ์ดํด์ด ์กด์ฌํ๋๋ผ๋, multiple instance๋ฅผ ๊ฐ์ง๋ค๋ฉด ๋ฐ๋๋ฝ์ด ๋ฌด์กฐ๊ฑด ๋ฐ์ํ๋ ๊ฒ์ด ์๋๊ธฐ ๋๋ฌธ์ด๋ค.
-
Banker's ์๊ณ ๋ฆฌ์ฆ์ ๋ฐ๋๋ฝ ๋ฐฉ์ง๋ฅผ ์ํด ํ ๋น ์์๋ฅผ ํ์ธํ๋ค.
- ์๋ก์ด ํ๋ก์ธ์ค๊ฐ ๋ค์ด์ค๋ฉด, ๊ฐ ์์ ์ ํ์ ์ธ์คํด์ค์ ์ต๋ ์๋ฅผ ๋ช ์ํด์ผ ํ๋ค.
- ์์ฒญ ์์ฑ ์, ์์ฒญ๋ ํ ๋น์ safe state์ ์๋ ์์คํ ์ ํ ๋นํ ์ง ๋๊ธฐ์ํฌ์ง ๊ฒฐ์ ํ๋ค.
-
ํ๋ก์ธ์ค๊ฐ ์์์ ์๊ตฌํ ๋ ์์คํ ์ ์์์ ํ ๋นํ ํ์๋ Safe state๋ก ๋จ์์๊ฒ ๋๋์ง๋ฅผ ์ฌ์ ์ ๊ฒ์ฌํ์ฌ ๋ฐ๋๋ฝ์ ํํผํ๋ ๋ฐฉ๋ฒ์ด๋ค.
- ๊ฒ์ฌํ์ฌ Safe state์ ์๋ค๋ฉด ์์์ ํ ๋นํ๊ณ , ๊ทธ๋ ์ง ์๋ค๋ฉด ๋ค๋ฅธ ํ๋ก์ธ์ค๋ค์ด ์์์ ํด์ ํ ๋๊น์ง ๋๊ธฐํ๋ค.